/*
https://leetcode-cn.com/problems/k-inverse-pairs-array/solution/kge-ni-xu-dui-shu-zu-by-leetcode-solutio-0hkr/
 */
public class Solution629 {
    private static final int mod = 1000000007;
    public int kInversePairs(int n, int k) {
        int[][] f=new int[2][k+1];
        f[0][0]=1;
        for (int i=1;i<=n;i++){
            for (int j=0;j<=k;j++){
                int cur=i&1,pre=cur^1;
                f[cur][j]=(j>=1?f[cur][j-1]:0)-(j>=i?f[pre][j-i]:0)+f[pre][j];
                while (f[cur][j]<0){
                    f[cur][j]+=mod;
                }
                while (f[cur][j]>=mod){
                    f[cur][j]-=mod;
                }
            }
        }
        return f[n&1][k];
    }

    public static void main(String[] args) {
        System.out.println(new Solution629().kInversePairs(3,1));
    }
}
